package removeelement;

import java.util.Arrays;

/**
 * @author XY
 * @version 1.0.0
 * @ClassName LC977.java
 * @createTime 2025年07月25日 19:19:00
 */
public class LC977 {

    /**
     * @Author XY
     * @Date 2025-07-26 11:55
     * @Param [nums]
     * @Return int[]
     * 这里返回数组从最后一个元素往前插入，因为这里从两端开始遍历，两端元素平方后的数组都是最大的数字，所以插入在数组最后面
     */
    public int[] sortedSquares(int[] nums) {
        int[] arr = new int[nums.length];
        int i = 0, j = nums.length - 1, index = nums.length - 1;
        //边界条件，可以等于j，此时处理最后一个元素，如果只有一个元素也能处理
        while (i <= j) {
            //每次把大的元素从后往前插入数组
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                arr[index] = nums[i] * nums[i];
                i++;
            } else {
                arr[index] = nums[j] * nums[j];
                j--;
            }
            index--;
        }
        return arr;
    }

    /**
     * @Author XY
     * @Date 2025-07-26 11:54
     * @Param [nums]
     * @Return int[]
     * 这里返回数组从0开始正序插入，因为是找的negative，也就是平方后最小的数字开始计算，所以从0下标开始往后插入
     */
    public int[] sortedSquares1(int[] nums) {
        int n = nums.length;
        int negative = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }
        int[] arr = new int[nums.length];
        //i为最小的负数下标，j为最小的正数下标，index是待插入的下标
        int i = negative, j = negative + 1, index = 0;
        //i<0说明所有的负数已经遍历完了，j>=n说明所有的正数已经遍历完了
        while (i >= 0 || j < n) {
            if (i < 0) {
                arr[index] = nums[j] * nums[j];
                j++;
            } else if (j == n) {
                arr[index] = nums[i] * nums[i];
                i--;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) {
                arr[index] = nums[i] * nums[i];
                i--;
            } else {
                arr[index] = nums[j] * nums[j];
                j++;
            }
            index++;
        }
        return arr;
    }

}
